題目

給一個字串 s，為一個tree的preorder，並在每個值之前用'-'表示此node的深度。
請還原這顆tree，並return root。

• Example
  
• Input: "1-2--3--4-5--6--7"
• Output: [1,2,5,3,4,6,7]

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

解法

• '-'告訴了我們深度。我們能根據深度，去還原tree。

• 使用DFS，這裡寫的是遞迴，參數有

  • node pointer的記憶體位址(很重要!)
  • 題目給的string (這不用說，一定要的)
  • string的idx (這樣才知道string走到哪了，當然也要傳位址，不然遞迴下去所存的idx就又不同了，
  • depth (這個就不需要位址了，不然每下一層就要+1，回來又要-1，所以就都保留著，讓此depth非遞迴下去的depth)。

• 先判斷idx走到底了沒。底了就return，因為結束了。

• 接著是算一下深度，'-'有幾個，跟目前所在深度符不符，符合才繼續，不然就return。

  • 要記得不要直接用idx去跑。因為不符合的話，idx不該前進。符合才會建立node。

• 符合的話，'-'一定都跑過了，s[idx]目前一定是存數字的字元，那我們就

  • 一樣的方式看value多長。
  • 將數字字串轉成int，
  • idx往後

• 接著建立node

• dfs重複這個過程，然後會傳root->left/root->right這個pointer的記憶體位址，所以建立node時。其實他們就已經連起來了，不用寫root->left= XXXX什麼的。

Code

class Solution {
private:
    void dfs(TreeNode*& root, string& s, int& idx, int depth){
        if(idx == s.size()){
            return;
        }
        
        int dep = 0;
        for(dep = 0; idx+dep < s.size()&& s[idx + dep]=='-'; dep++);
        if(dep != depth){
            return;
        }
        idx += dep;
        
        int val_length = 0;
        for(val_length = 0; idx+val_length < s.size() && isdigit(s[idx + val_length]); val_length++);
        int val = stoi(s.substr(idx, val_length));
        idx += val_length;
     
        root = new TreeNode(val);
        
        dfs(root->left, s, idx, depth + 1);
        dfs(root->right, s, idx, depth + 1);
    }
public:    
    TreeNode* recoverFromPreorder(string S) {
        TreeNode* root = nullptr;
        dfs(root, S, *new int(0), 0);
        return root;
    }
};